package example;

public class Insertion {
    private Insertion() {}


    public static <E extends Comparable<E>> void sort(E[] data, int l, int r) {
        for (int i = l; i <= r; i++) {
            int j = i;
            E e = data[i];
            while (j > 0 && data[j - 1].compareTo(e) > 0) { // 前面有元素, 并且前面的元素大于e
                data[j] = data[j - 1];
                j--;
            }
            data[j] = e;
        }
    }

    public static void main(String[] args) {
        Integer[] data = Utils.randomArray(100, 100);
        Utils.timeSpent(Insertion::sort, "插入排序", data, 0, data.length -1);
    }
}
